#include <iostream>
#include <vector>
#include <algorithm>
#include <Vector.hpp>

using namespace std;

class Solution
{
public:
    vector<vector<int>> combinationSum(vector<int> &candidates, int target)
    {
        vector<vector<int>> res;
        vector<int> path;
        sort(candidates.begin(), candidates.end(), less<int>());
        bt(candidates, 0, target, path, res);
        return res;
    }

    void bt(vector<int> &candidates, int lastIndex, int target, vector<int> &path, vector<vector<int>> &res)
    {
        for (int i = lastIndex; i < candidates.size(); i++)
        {
            if (candidates[i] > target)
            {
                return;
            }
            if (candidates[i] == target)
            {
                res.push_back(path);
                res.back().push_back(candidates[i]);
                return;
            }
            if (candidates[lastIndex] > target - candidates[i])
            {
                continue;
            }
            path.push_back(candidates[i]);
            bt(candidates, i, target - candidates[i], path, res);
            path.pop_back();
        }
    }
};

int main()
{
    cout << "Code39" << endl;
    Solution s;
    vector<int> candidates = {2, 3, 6, 7};
    int target = 7;
    vector<vector<int>> res = s.combinationSum(candidates, target);
    Print2DVector(res);
    return 0;
}